#include <iostream>
#include <random>

struct Node {
  int ls, rs, sz;
  unsigned rnd;
  long long val, sum;
  __int128_t xsum;
} tr[400007];
int nodecnt;
inline int pushup(int p) {
  tr[p].sz = tr[tr[p].ls].sz + 1 + tr[tr[p].rs].sz;
  tr[p].sum = tr[tr[p].ls].sum + tr[p].val + tr[tr[p].rs].sum;
  tr[p].xsum = tr[tr[p].ls].xsum + tr[p].val * (tr[tr[p].ls].sz + __int128_t(1)) + tr[tr[p].rs].xsum + tr[tr[p].rs].sum * (tr[tr[p].ls].sz + __int128_t(1));
  return p;
}
std::pair<int, int> split_by_sz(int p, int sz) {
  if (p == 0) {
    return {0, 0};
  }
  if (tr[tr[p].ls].sz < sz) {
    auto [m, r] = split_by_sz(tr[p].rs, sz - 1 - tr[tr[p].ls].sz);
    tr[p].rs = m;
    return {pushup(p), r};
  }
  auto [l, m] = split_by_sz(tr[p].ls, sz);
  tr[p].ls = m;
  return {l, pushup(p)};
}
std::pair<int, int> split_by_val(int p, long long val) {
  if (p == 0) {
    return {0, 0};
  }
  if (tr[p].val <= val) {
    auto [m, r] = split_by_val(tr[p].rs, val);
    tr[p].rs = m;
    return {pushup(p), r};
  }
  auto [l, m] = split_by_val(tr[p].ls, val);
  tr[p].ls = m;
  return {l, pushup(p)};
}
int merge(int u, int v) {
  if (u == 0 || v == 0) {
    return u + v;
  }
  if (tr[u].rnd < tr[v].rnd) {
    tr[u].rs = merge(tr[u].rs, v);
    return pushup(u);
  }
  tr[v].ls = merge(u, tr[v].ls);
  return pushup(v);
}
std::mt19937 rng(0x3b800001);
int root;
void insert(long long x) {
  ++nodecnt;
  tr[nodecnt].sum = tr[nodecnt].xsum = tr[nodecnt].val = x;
  tr[nodecnt].rnd = rng();
  tr[nodecnt].sz = 1;
  auto [l, r] = split_by_val(root, x);
  root = merge(l, merge(nodecnt, r));
}
bool erase(long long x) {
  auto [lm, r] = split_by_val(root, x);
  auto [l, m] = split_by_val(lm, x - 1);
  if (m == 0) {
    root = merge(l, r);
    return false;
  }
  root = merge(l, r);
  return true;
}
long long getsum(int x) {
  auto [l, r] = split_by_sz(root, x);
  auto ans = tr[l].sum;
  root = merge(l, r);
  return ans;
}
void write(__int128_t x) {
  std::vector<int> v;
  while (x != 0) {
    v.push_back(x % 10);
    x /= 10;
  }
  if (v.empty()) {
    v = {0};
  }
  for (int i = int(v.size()) - 1; i >= 0; --i) {
    std::cout << v[i];
  }
  std::cout << '\n';
}
void solve() {
  int n = tr[root].sz;
  int l = 2, r = (n + 1) >> 1, L = -1, R;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (getsum(mid) + getsum(n - mid + 1) <= tr[root].sum) {
      r = (L = mid) - 1;
    } else {
      l = mid + 1;
    }
  }
  __int128_t ans = 0;
  if (L == -1) {
    L = 1, R = 0;
  } else {
    R = n + 1 - L, --L;
    ans += tr[root].sum - getsum(n - R);
    ans -= getsum(L);
  }
  auto FFFF = [&](int jjj, int sgn) {
    ++jjj;
    {
      auto [lNode, rNode] = split_by_sz(root, jjj - 1);
      ans += (tr[lNode].xsum - __int128_t(jjj) * tr[lNode].sum) * sgn;
      root = merge(lNode, rNode);
    }
    {
      auto [lNode, rNode] = split_by_sz(root, n - jjj + 1);
      ans += tr[rNode].xsum * sgn;
      root = merge(lNode, rNode);
    }
  };
  FFFF(L - 1, +1), FFFF(n - 1, +1), FFFF(R, -1);
  std::cout << ans << '\n';
  write(ans);
}

int main() {
  std::freopen("kte.in", "r", stdin);
  std::freopen("kte.out", "w", stdout);
  std::cin.tie(nullptr)->sync_with_stdio(false);
  int n = 4e5;
  std::cin >> n;
  while (n--) {
    long long x = std::uniform_int_distribution<long long>(1, 1e12)(rng);
    std::cin >> x;
    if (!erase(x)) {
      insert(x);
    }
    solve();
  }
  return 0;
}